﻿public class Solution {
    public int LargestRectangleArea(int[] heights)
    {
        // 收尾添加0
        List<int> heightList = new List<int>(heights);
        heightList.Add(0);
        heightList.Insert(0, 0);
        
        // 单调栈问题
        int res = 0; // 记录结果
        Stack<int> stack = new Stack<int>();
        for (int i = 0; i < heightList.Count; i++)
        {
            while (stack.Count > 0)
            {
                int top = stack.Peek();

                if (heightList[top] == heightList[i])
                {
                    stack.Pop();
                    break;
                }

                if (heightList[top] > heightList[i])
                {
                    int mid = stack.Pop();
                    int left = stack.Peek();

                    int area = heightList[mid] * (i - left - 1);
                    res = res < area ? area : res;
                }
                else break;
            }
            stack.Push(i);
        }
        return res;
    }

    public static void Main(string[] args)
    {
        int[] heights = [2, 1, 5, 6, 2, 3];
        Solution solution = new Solution();
        int res = solution.LargestRectangleArea(heights);
        Console.WriteLine(res);
    }
}